Programmable logic devices (PLDs) are a well-known type of integrated circuit that can be programmed to perform specified logic functions. One type of PLD, the Complex Programmable Logic Device (CPLD), typically includes two or more logic blocks (function blocks) interconnected by an interconnect switch matrix, or routing matrix. Each function block of the CPLD includes a two-level AND/OR structure similar to those used in Programmable Logic Arrays (PLAs) and Programmable Array Logic (PAL) devices. In CPLDs, configuration data is typically stored on-chip in non-volatile memory. In some CPLDs, configuration data is stored on-chip in non-volatile memory, then downloaded to volatile memory as part of an initial configuration sequence.
Another type of PLD is the Field Programmable Gate Array, or FPGA. An FPGA also includes both programmable logic blocks and a programmable interconnect structure interconnecting the logic blocks. The programmable functions in FPGAs are most commonly controlled by configuration data stored in static memory cells.
Other PLDs are programmed by applying a processing layer, such as a metal layer, that programmably interconnects the various elements on the device. These PLDs are known as mask programmable devices. PLDs can also be implemented in other ways, e.g., using fuse or antifuse technology. The terms “PLD” and “programmable logic device” include but are not limited to these exemplary devices, as well as encompassing devices that are only partially programmable.
FIG. 1 illustrates an exemplary well-known CPLD. The CPLD of FIG. 1 includes a routing matrix (RM) 101, a plurality of function blocks 102–102n, a corresponding plurality of input/output (I/O) blocks (IOBs) 103–103n, and supporting logic such as boundary scan and in-system programming logic (BSC & ISP) 106. I/O pads 104–104n are coupled to respective IOBs 103–103n, which in turn communicate with function blocks 102–102n. Function blocks 102–102n communicate with routing matrix 101. Each function block includes a PLA AND/OR plane and a plurality of macrocells MC1–MC16.
Clock and control signals (CLOCK & CTRL SIGNALS) 109 are provided to function blocks 102–102n and I/O blocks 103–103n. In some CPLDs, a boundary scan path (BSC PATH) 108 connects the I/O blocks 103–103n in a boundary scan chain for testing and/or programming purposes via boundary scan I/O pads 107. In some CPLDs, fast input connections 105–105n optionally provide faster interconnections between IOBs 103–103n, function blocks 102–102n, and routing matrix 101. (Note that in the present specification, the same reference characters are used to refer to terminals, signal lines, and their corresponding signals.)
Clearly, the larger the number of programmable interconnections provided by routing matrix 101, the easier it will be to implement large amounts of logic in the CPLD, e.g., fully utilizing all of the available macrocells and function blocks. However, an overly large routing matrix, such as a routing matrix providing every possible interconnection between every input terminal and every output terminal of the matrix, would adversely affect the cost of the CPLD. Therefore, most CPLDs support only a subset of the possible interconnections, as shown, for example, in FIGS. 2–3.
FIG. 2 illustrates a small routing matrix having twelve input signals 0–11 and six output signals MUX0 through MUX5. Output signals MUX0 through MUX5 are provided by six corresponding multiplexers 200–205. Each of multiplexers 200–205 has four input signals selected from the twelve input signals 0–11. The selection of an input signal as an input to a multiplexer is shown as an open circle (e.g., circle 206) at the intersection of the signal line and the input line to the multiplexer. For example, output signal MUX0 is provided by multiplexer 200 from any of input signals 0, 3, 6, and 9. Multiplexers 201–205 are driven by their selected input signals as shown in FIG. 2.
FIG. 3 illustrates the same routing matrix as FIG. 2, but in the form of a routing matrix pattern. By comparing FIGS. 2 and 3, it is clear that each numerical value in routing matrix pattern 300 corresponds to one of the input signals 0–11 shown in FIG. 2, and each row of values in routing matrix pattern 300 corresponds to a set of input terminals coupled to a different multiplexer 200–205 to provide output signals MUX0–MUX5.
The exemplary routing matrix shown in FIGS. 2 and 3 is a straightforward implementation that provides little routing flexibility. There are many routing combinations (corresponding to many logical circuits) that cannot be routed using the pictured routing matrix. For example, if a CPLD user wishes to route the three input signals 0, 3, and 6 to three of the output multiplexers, the design will fail to route. In this example, signal 0 can be routed to output terminal MUX0, and signal 3 can be routed to output terminal MUX3, but signal 6 cannot be provided to any of the remaining output terminals MUX1, MUX2, MUX4, or MUX5.
FIGS. 4 and 5 illustrate a more versatile routing matrix than that of FIGS. 2 and 3. As shown in FIG. 4, this routing matrix is the same size as that of the previous example, also having twelve input signals 0–11 and six output signals MUX0 through MUX5. Output signals MUX0 through MUX5 are provided by six corresponding multiplexers 400–405. Each of multiplexers 400–405 has four input signals selected from the twelve input signals 0–11. Again, the selection of an input signal as an input to a multiplexer is shown as an open circle (e.g., circle 406) at the intersection of the signal line and the input line to the multiplexer. For example, output signal MUX0 is provided by multiplexer 400 from any of input signals 0, 3, 6, and 11. Multiplexers 401–405 are driven by their selected input signals as shown in FIG. 4.
FIG. 5 illustrates the same routing matrix as FIG. 4, but in the form of a routing matrix pattern. By comparing FIGS. 4 and 5, it is clear that each numerical value in routing matrix pattern 500 corresponds to one of the input signals 0–11 shown in FIG. 4, and each row of values in routing matrix pattern 500 corresponds to a set of input terminals coupled to a different multiplexer 400–405 to provide output signals MUX0–MUX5.
Note that the less repetitive nature of the selected signals in the example of FIGS. 4–5 results in a more flexible routing matrix. For example, unlike the routing matrix of FIGS. 2 and 3, the routing matrix of FIGS. 4 and 5 can route the three signals 0, 3, and 6 successfully. Signal 0 can be routed to output terminal MUX0, signal 3 can be routed to output terminal MUX5, and signal 6 can be routed to output terminal MUX4.
The routing matrix illustrated in FIGS. 4 and 5 is flexible, but it is also small. Deriving a suitable pattern of programmable interconnections is relatively simple for a routing matrix of this size. However, PLD routing matrices are typically much larger than these simple examples. Further, it is frequently desirable to produce “families” of related PLDs having routing matrices of varying sizes. Each routing matrix must be laid out, and routing software must be developed to support each of the routing matrices. Therefore, the process of creating and supporting routing matrices for each member of a PLD family can be a significant task. It is desirable, therefore, to provide methods of implementing routing matrices that simplify these tasks while providing flexible routing options to the PLD user.